#include <vector>
#include <iostream>

using namespace std;

template <typename T>
class Node {
public:
  Node (T value, Node *left = nullptr, Node *right = nullptr, int n = 1)
    :value(value), left(left), right(right), n(n) {}

  T value;
  Node *left;
  Node *right;
  int n; // Nodes rooted at this Node
};

template <typename T>
class BST {
public:
  BST() : root(nullptr){}
  
  BST(const vector<T> &v) {
    root = put(nullptr, v[0]);

    for (int i = 1; i < v.size(); ++i) {
      put(v[i]);
    }
  }

  int size() { return size(root); }

  void put(T val) {
    put(root, val);
  }

  void preOrder() { preOrder(root); }

private:
  int size(Node<T> *pNode) {
    return pNode == nullptr ? 0 : pNode->n;
  }

  Node<T> *put(Node<T> *pNode, T val) {
    if (pNode == nullptr) {
      return new Node {val};
    }

    if (val < pNode->value) {
      pNode->left = put(pNode->left, val);
    }
    else if (val > pNode->value) {
      pNode->right = put(pNode->right, val);
    }
    else {
      pNode->value = val;
    }

    pNode->n = size(pNode->left) + size(pNode->right) + 1;
    return pNode;
  }

  void preOrder(Node<T> *pNode) {
    if (pNode == nullptr) { return; }

    cout << pNode->value << " ";
    preOrder(pNode->left);
    preOrder(pNode->right);
  }

  Node<T> *deleteMin(Node<T> *pNode) {
    if (pNode->left == nullptr) {
      Node *p = pNode->right;
      delete pNode;
      return p;
    }

    pNode->left = deleteMin(pNode->left);
    return pNode;
  }
private:
  Node<T> *root;
};

int main(int argc, char const *argv[])
{
  vector<int> v {5, 1, 9, 2, 7, 6, 8};

  BST<int> tree(v);
  tree.preOrder();
  return 0;
}

